package com.javaGather.demo;

public class LinkedListDemo<E> {

    /**
     * 头指针，尾指针，节点个数
     */
    private Node<E> first;
    private Node<E> last;
    private int size = 0;

    private static class Node<E> {
        private E item;
        private Node<E> next;
        private Node<E> prev;


        /**
         * @param prev    当前节点上一个节点
         * @param element 当前节点的值
         * @param next    当前节点下一个节点
         */
        public Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    //添加方法
    public void add(E e) {

        //当前链表最后一个节点
        Node l = last;

        //新创建的节点，上一个节点为链表最后一个节点
        Node<E> newNode = new Node<E>(l, e, null);

        // 尾节点指向新建节点
        last = newNode;

        //链表为空
        if (l == null) {
            // 头指针指向新建节点
            first = newNode;
        } else {
            //链表不为空
            //尾节点.next指向新建节点
            l.next = newNode;
        }
        size++;
    }

    public E get(int index) {
        return node(index).item;
    }


    //折半查找
    Node<E> node(int index) {
        //判断下标是否越界
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> node;
        if (index < (size >> 1)) {
            node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
        }
        return node;
    }
}
